package likou.tanxin;

import java.util.*;
import java.util.stream.Collectors;

/**
 * @Info:
 * @Author: 唐小尊
 * @Date: 2020/10/09 14:27
 */
public class _502 {
    public static void main(String[] args) {
        System.out.println(findMaximizedCapital2(2,0,new int[]{1,2,3},new int[]{0,1,1}));
    }
    public static int findMaximizedCapital(int k, int W, int[] Profits, int[] Capital) {
        int daan = W;
        List<int[]> list = new ArrayList<>();
        for (int i = 0; i < Profits.length; i++) {
            int[] ints = new int[]{Profits[i],Capital[i]};
            list.add(ints);
        }
        list.sort(Comparator.comparingInt((int[] o) -> o[1]));

        while (k>0&&list.size()>0){
            k--;
            boolean p = true;
            int max = 0;
            int maxI = 0;
            for (int i = 0; i < list.size(); i++) {
                if (list.get(i)[1]<=daan&&list.get(i)[0]>=max){
                    max = list.get(i)[0];
                    maxI = i;
                    p = false;
                }else if (list.get(i)[1]>daan){
                    break;
                }
            }
            daan += max;
            list.remove(maxI);
            if (p){
                break;
            }
        }
        return daan-W;
    }

    /**
     * 创建一个预备数组
     * @param k
     * @param W
     * @param Profits
     * @param Capital
     * @return
     */
    public static int findMaximizedCapital2(int k, int W, int[] Profits, int[] Capital) {
        int daan = W;
        List<int[]> list = new ArrayList<>();
        for (int i = 0; i < Profits.length; i++) {
            int[] ints = new int[]{Profits[i],Capital[i]};
            list.add(ints);
        }
        int finalDaan = daan;
        List<int[]> now = list.stream().filter((int[] o)-> o[1]<= finalDaan).collect(Collectors.toList());
        list.removeAll(now);
        List<int[]> listYuBei = new ArrayList<>(now);
        listYuBei.sort((int[] o1, int[] o2) -> o2[0]-o1[0]);

        while (k>0&&listYuBei.size()>0){
            k--;
            daan += listYuBei.get(0)[0];
            listYuBei.remove(0);

            if(list.size()>0){
                int finalDaan1 = daan;
                now = list.stream().filter((int[] o)-> o[1]<= finalDaan1).collect(Collectors.toList());
                list.removeAll(now);
                listYuBei.addAll(now);
                listYuBei.sort((int[] o1, int[] o2) -> o2[0]-o1[0]);
            }else{
                int p = 0;
                while(k>0){
                    k--;
                    daan+=listYuBei.get(p)[0];
                    p++;
                }
            }
        }
        return daan;
    }
    public int findMaximizedCapital3(int k, int W, int[] Profits, int[] Capital) {
        // 加快：如果所有项目都可用
        boolean speedUp = true;
        //遍历一遍
        for (int c: Capital) {
            if (W < c) {
                speedUp = false;
            }
        }
        if (speedUp) {
            PriorityQueue<Integer> heap = new PriorityQueue<>();
            for (int p: Profits) {
                heap.add(p);
                if (heap.size() > k) {
                    heap.poll();
                }
            }
            for (int h: heap) {
                W += h;
            }
            return W;
        }


        int idx;
        int n = Profits.length;
        for(int i = 0; i < Math.min(k, n); ++i) {
            idx = -1;
            // 如果有可用的项目
            // 选择最赚钱的
            for(int j = 0; j < n; ++j) {
                if (W >= Capital[j]) {
                    if (idx == -1 ) {
                        idx = j;
                    } else if (Profits[idx] < Profits[j]) {
                        idx = j;
                    }
                }
            }
            // 没有足够的资金来启动任何项目
            if(idx == -1) {
                break;
            }

            // 添加所选项目的利润
            // 并从进一步考虑中删除该项目
            W += Profits[idx];
            Capital[idx] = Integer.MAX_VALUE;
        }
        return  W;
    }
}
